{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Construct Binary Tree from Inorder and Postorder Traversal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #array #hash-table #divide-and-conquer #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #数组 #哈希表 #分治 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: buildTree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #从中序与后序遍历序列构造二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个整数数组 <code>inorder</code> 和 <code>postorder</code> ，其中 <code>inorder</code> 是二叉树的中序遍历， <code>postorder</code> 是同一棵树的后序遍历，请你构造并返回这颗&nbsp;<em>二叉树</em>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/02/19/tree.jpg\" />\n",
    "<pre>\n",
    "<b>输入：</b>inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]\n",
    "<b>输出：</b>[3,9,20,null,null,15,7]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>inorder = [-1], postorder = [-1]\n",
    "<b>输出：</b>[-1]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= inorder.length &lt;= 3000</code></li>\n",
    "\t<li><code>postorder.length == inorder.length</code></li>\n",
    "\t<li><code>-3000 &lt;= inorder[i], postorder[i] &lt;= 3000</code></li>\n",
    "\t<li><code>inorder</code>&nbsp;和&nbsp;<code>postorder</code>&nbsp;都由 <strong>不同</strong> 的值组成</li>\n",
    "\t<li><code>postorder</code>&nbsp;中每一个值都在&nbsp;<code>inorder</code>&nbsp;中</li>\n",
    "\t<li><code>inorder</code>&nbsp;<strong>保证</strong>是树的中序遍历</li>\n",
    "\t<li><code>postorder</code>&nbsp;<strong>保证</strong>是树的后序遍历</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [construct-binary-tree-from-inorder-and-postorder-traversal](https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [construct-binary-tree-from-inorder-and-postorder-traversal](https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[9,3,15,20,7]\\n[9,15,7,20,3]', '[-1]\\n[-1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        inorder = sorted(preorder)\n",
    "        def buildTree(preorder, inorder):\n",
    "            if preorder:\n",
    "                root = TreeNode(preorder[0])\n",
    "                i = inorder.index(preorder[0])\n",
    "                root.left = buildTree(preorder[1:i+1], inorder[:i])\n",
    "                root.right = buildTree(preorder[i+1:], inorder[i+1:])\n",
    "                return root\n",
    "            return\n",
    "\n",
    "        return buildTree(preorder, inorder)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        def buildTree(preorder: List[int]) -> Optional[TreeNode]:\n",
    "            if not preorder: return\n",
    "            root = TreeNode(val = preorder[0])\n",
    "            preorderLeft = []\n",
    "            preorderRight = []\n",
    "            for oneNode in preorder[1:]:\n",
    "                if oneNode < preorder[0]:\n",
    "                    preorderLeft.append(oneNode)\n",
    "                else:\n",
    "                    preorderRight.append(oneNode)\n",
    "            root.left = buildTree(preorderLeft)\n",
    "            root.right = buildTree(preorderRight)\n",
    "            return root\n",
    "        return buildTree(preorder)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        # # 1. 二叉搜索树的中序遍历是递增的\n",
    "        # inorder = sorted(preorder)\n",
    "        # def buildTree(preorder, inorder):\n",
    "        #     if preorder:\n",
    "        #         root = TreeNode(preorder[0])\n",
    "        #         i = inorder.index(preorder[0])\n",
    "        #         root.left = buildTree(preorder[1:i+1], inorder[:i])\n",
    "        #         root.right = buildTree(preorder[i+1:], inorder[i+1:])\n",
    "        #         return root\n",
    "        #     return\n",
    "        # return buildTree(preorder, inorder)\n",
    "        # 2.小于根节点的都是左子树\n",
    "        def buildTree(preorder, start, end):\n",
    "            if start==end:return None\n",
    "            root = TreeNode(preorder[start])\n",
    "            leftEnd = start+1\n",
    "            while leftEnd<end and preorder[leftEnd]<preorder[start]:\n",
    "                leftEnd+=1\n",
    "            root.left = buildTree(preorder, start+1, leftEnd)\n",
    "            root.right = buildTree(preorder, leftEnd, end)\n",
    "            return root\n",
    "        return buildTree(preorder, 0, len(preorder))\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self, postorder, inorder):\n",
    "        if len(inorder) == 0:\n",
    "            return None\n",
    "        root = TreeNode(postorder.pop())\n",
    "        rootInorderIndex = inorder.index(root.val)\n",
    "        \n",
    "        leftInorder = inorder[:rootInorderIndex]\n",
    "        rightInorder = inorder[rootInorderIndex + 1:]\n",
    "        \n",
    "        root.right = self.dfs(postorder, rightInorder)\n",
    "        root.left = self.dfs(postorder, leftInorder)\n",
    "        return root\n",
    "    \n",
    "        \n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        return self.dfs(postorder, inorder)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: 'List[int]', postorder: 'List[int]') -> 'TreeNode':\n",
    "        dic = {}\n",
    "        for i,ele in enumerate(inorder):\n",
    "            dic[ele] = i\n",
    "        head = None\n",
    "        stack = []\n",
    "        for i in range(len(postorder)-1,-1,-1):\n",
    "            if not head:\n",
    "                head = TreeNode(postorder[i])\n",
    "                stack.append(head)\n",
    "            else:\n",
    "                num = postorder[i]\n",
    "                idx = dic[num]\n",
    "                node = TreeNode(num)\n",
    "                if idx > dic[stack[-1].val]:\n",
    "                    stack[-1].right = node\n",
    "                else:\n",
    "                    u = stack.pop()\n",
    "                    while stack and dic[stack[-1].val] > idx:\n",
    "                        u = stack.pop()\n",
    "                    u.left = node\n",
    "                stack.append(node)\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, inorder, postorder):\n",
    "        \"\"\"\n",
    "        :type inorder: List[int]\n",
    "        :type postorder: List[int]\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        return self.helper(0, len(inorder)-1, 0, len(postorder)-1, inorder, postorder)\n",
    "\n",
    "    def helper(self, in_start, in_end, post_start, post_end, in_order, post_order):\n",
    "        if in_start > in_end or post_start > post_end:\n",
    "            return None\n",
    "        root = TreeNode(post_order[post_end])\n",
    "        rootIndex = post_end\n",
    "        for i in range(in_start, in_end+1):\n",
    "            if in_order[i] == post_order[rootIndex]:\n",
    "                rootIndex = i\n",
    "                break\n",
    "\n",
    "        root.left = self.helper(in_start, rootIndex-1, post_start, post_start+rootIndex-in_start-1, in_order, post_order)\n",
    "        root.right = self.helper(rootIndex+1, in_end, post_start+rootIndex-in_start, post_end-1, in_order, post_order)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution(object):\n",
    "    def buildTree(self, inorder, postorder):\n",
    "        \"\"\"\n",
    "        :type inorder: List[int]\n",
    "        :type postorder: List[int]\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        def helper(inorder, a, b, postorder, c, d):\n",
    "            if a > b:\n",
    "                return None\n",
    "            v = postorder[d]\n",
    "            root = TreeNode(v)\n",
    "            idx = a\n",
    "            for i in range(a, b + 1):\n",
    "                if inorder[i] == v:\n",
    "                    idx = i\n",
    "                    break\n",
    "            root.left = helper(inorder, a, idx - 1, postorder, c, c + idx - 1 - a)\n",
    "            root.right = helper(inorder, idx + 1, b, postorder, c + idx - a, d - 1)\n",
    "            return root\n",
    "        return helper(inorder, 0, len(inorder) - 1, postorder, 0, len(postorder) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:\n",
    "        if not postorder:\n",
    "            return None\n",
    "        post_id = len(postorder) - 2\n",
    "        in_id = len(inorder) - 1\n",
    "        root = TreeNode(postorder[-1])\n",
    "        cur = root\n",
    "        visit = []\n",
    "        visit.append(cur)\n",
    "        while post_id >= 0:\n",
    "            if (cur.val == inorder[in_id]) :\n",
    "                while visit and visit[-1].val == inorder[in_id] :\n",
    "                    cur = visit.pop()\n",
    "                    in_id = in_id - 1\n",
    "                cur.left = TreeNode(postorder[post_id])\n",
    "                cur = cur.left\n",
    "                visit.append(cur)\n",
    "                post_id = post_id - 1\n",
    "            else :\n",
    "                cur.right = TreeNode(postorder[post_id])\n",
    "                cur = cur.right\n",
    "                visit.append(cur)\n",
    "                post_id = post_id - 1\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:\n",
    "        if not postorder:\n",
    "            return None\n",
    "        if len(postorder) == 1:\n",
    "            d = TreeNode(postorder[0])\n",
    "            return d\n",
    "        if postorder == inorder:\n",
    "            prev = None\n",
    "            head = None\n",
    "            for i in inorder[::-1]:\n",
    "                d = TreeNode(i)\n",
    "                if not head:\n",
    "                    head = d\n",
    "                if prev:\n",
    "                    prev.left = d\n",
    "                prev = d\n",
    "            return head\n",
    "        if inorder[::-1] == postorder:\n",
    "            prev = None\n",
    "            head = None\n",
    "            for i in inorder:\n",
    "                d = TreeNode(i)\n",
    "                if not head:\n",
    "                    head = d\n",
    "                if prev:\n",
    "                    prev.right = d\n",
    "                prev = d\n",
    "            return head\n",
    "        d = TreeNode(postorder[-1])\n",
    "        root = inorder.index(postorder[-1])\n",
    "        left_inorder = inorder[0:root]\n",
    "        left_postorder = []\n",
    "        for i in postorder:\n",
    "            if i in left_inorder:\n",
    "                left_postorder.append(i)\n",
    "        right_inorder = inorder[root+1:]\n",
    "        right_postorder = []\n",
    "        for i in postorder:\n",
    "            if i in right_inorder:\n",
    "                right_postorder.append(i)\n",
    "        d.left = self.buildTree(left_inorder, left_postorder)\n",
    "        d.right = self.buildTree(right_inorder, right_postorder)\n",
    "        return d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:\n",
    "        if not postorder:\n",
    "            return None\n",
    "        n = len(postorder)\n",
    "        root = TreeNode(postorder[n-1])\n",
    "        stack = [root]\n",
    "        inorderIndex = n-1\n",
    "        for i in range(n-2,-1,-1):\n",
    "            node = stack[-1]\n",
    "            posValue = postorder[i]\n",
    "            if node.val!=inorder[inorderIndex]:\n",
    "                node.right = TreeNode(posValue)\n",
    "                stack.append(node.right)\n",
    "            else:\n",
    "                while stack and stack[-1].val==inorder[inorderIndex]:\n",
    "                    inorderIndex-=1\n",
    "                    node = stack.pop()\n",
    "                node.left = TreeNode(posValue)\n",
    "                stack.append(node.left)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        root=TreeNode(postorder[-1])\n",
    "        cur=len(inorder)-1\n",
    "        stack=[root]\n",
    "        for i in range(len(postorder)-2,-1,-1):\n",
    "            newnode=TreeNode(postorder[i])\n",
    "            if stack[-1].val!=inorder[cur]:\n",
    "                stack[-1].right=newnode\n",
    "                stack.append(newnode)\n",
    "            else:\n",
    "                while stack and stack[-1].val==inorder[cur]:\n",
    "                    node=stack.pop()\n",
    "                    cur-=1\n",
    "                node.left=newnode\n",
    "                stack.append(newnode)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not postorder:\n",
    "            return None\n",
    "        \n",
    "        n = len(postorder)\n",
    "        root = TreeNode(postorder[n - 1])\n",
    "        stack = [root]\n",
    "        inorder_idx = n - 1\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            postorder_val = postorder[i]\n",
    "            node = stack[-1]\n",
    "            if node.val != inorder[inorder_idx]:\n",
    "                node.right = TreeNode(postorder_val)\n",
    "                stack.append(node.right)\n",
    "            else:\n",
    "                while stack and stack[-1].val == inorder[inorder_idx]:\n",
    "                    node = stack.pop()\n",
    "                    inorder_idx -= 1\n",
    "                node.left = TreeNode(postorder_val)\n",
    "                stack.append(node.left)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        stack = collections.deque()\n",
    "        n = len(postorder)\n",
    "        stack.append([(0, n), (0, n), None, 'root'])\n",
    "        ans = None\n",
    "        while stack:\n",
    "            # print(stack)\n",
    "            # func body\n",
    "            # func input\n",
    "            postorder_section, inorder_section, parent, flag = stack.pop()\n",
    "            # recursion boundary\n",
    "            if postorder_section[1] - postorder_section[0] < 1:\n",
    "                continue\n",
    "\n",
    "            # create node\n",
    "            val = postorder[postorder_section[1]-1]\n",
    "            x = TreeNode(val)\n",
    "\n",
    "            # divide lc and rc subtree\n",
    "            idx = inorder.index(val, inorder_section[0], inorder_section[1])\n",
    "            lc_len = idx - inorder_section[0]\n",
    "\n",
    "            lc_postorder_section = (postorder_section[0], postorder_section[0] + lc_len)\n",
    "            rc_postorder_section = (postorder_section[0] + lc_len, postorder_section[1]-1)\n",
    "\n",
    "            lc_inorder_section = (inorder_section[0], idx)\n",
    "            rc_inorder_section = (idx+1, inorder_section[1])\n",
    "\n",
    "            # call func for lc and rc\n",
    "            stack.append([rc_postorder_section, rc_inorder_section, x, 'rc'])\n",
    "            stack.append([lc_postorder_section, lc_inorder_section, x, 'lc'])\n",
    "\n",
    "\n",
    "            # return node\n",
    "            if flag == 'lc':\n",
    "                parent.left = x\n",
    "            elif flag == 'rc':\n",
    "                parent.right = x\n",
    "            elif flag == 'root':\n",
    "                ans = x\n",
    "        return ans\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        def build(l, r):\n",
    "            if l == r: return None\n",
    "            idx = max(indices[l:r])[1]\n",
    "            return TreeNode(inorder[idx], build(l, idx), build(idx+1, r))\n",
    "\n",
    "        indices = [(postorder.index(x), i) for i,x in enumerate(inorder)]\n",
    "        return build(0, len(inorder))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        def helper(in_left, in_right):\n",
    "            # 如果这里没有节点构造二叉树了，就结束\n",
    "            if in_left > in_right:\n",
    "                return None\n",
    "            \n",
    "            # 选择 post_idx 位置的元素作为当前子树根节点\n",
    "            val = postorder.pop()\n",
    "            root = TreeNode(val)\n",
    "\n",
    "            # 根据 root 所在位置分成左右两棵子树\n",
    "            index = idx_map[val]\n",
    " \n",
    "            # 构造右子树\n",
    "            root.right = helper(index + 1, in_right)\n",
    "            # 构造左子树\n",
    "            root.left = helper(in_left, index - 1)\n",
    "            return root\n",
    "        \n",
    "        # 建立（元素，下标）键值对的哈希表\n",
    "        idx_map = {val:idx for idx, val in enumerate(inorder)} \n",
    "        return helper(0, len(inorder) - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        ind=dict(zip(inorder,range(len(inorder))))\n",
    "        postd=dict(zip(postorder,range(len(postorder))))\n",
    "        def func(inos,inoe,pos,poe):\n",
    "            if pos>poe or inos>inoe:\n",
    "                return None\n",
    "            else:\n",
    "                res=TreeNode()\n",
    "                res.val=postorder[poe]\n",
    "                lins=inos\n",
    "                line=ind[postorder[poe]]-1\n",
    "                rins=ind[postorder[poe]]+1\n",
    "                rine=inoe\n",
    "\n",
    "                lpos=pos\n",
    "                lpoe=pos+ind[postorder[poe]]-inos-1\n",
    "                rpos=lpoe+1\n",
    "                rpoe=poe-1\n",
    "                res.left=func(lins,line,lpos,lpoe)\n",
    "                res.right=func(rins,rine,rpos,rpoe)\n",
    "                return res\n",
    "        return func(0,len(inorder)-1,0,len(postorder)-1)\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        def build(inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "            #print(inorder,postorder)\n",
    "            lenth = len(inorder)\n",
    "            if lenth==1: return TreeNode(inorder[0])\n",
    "            value = postorder.pop()\n",
    "            root = TreeNode(value)\n",
    "            for i in range(lenth):\n",
    "                if inorder[i]==value:\n",
    "                    index = i\n",
    "            if index >0:\n",
    "                lefti = collections.deque()\n",
    "                leftp = collections.deque()\n",
    "                for _ in range(index):\n",
    "                    lefti.append(inorder.popleft())\n",
    "                    leftp.append(postorder.popleft())\n",
    "                root.left = build(lefti, leftp)\n",
    "            if index<lenth-1:\n",
    "                inorder.popleft()\n",
    "                righti = inorder\n",
    "                rightp = postorder\n",
    "                root.right = build(righti, rightp)\n",
    "            return root\n",
    "        ans = build(collections.deque(inorder),collections.deque(postorder))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        stack = []\n",
    "        n = len(inorder)\n",
    "        stack.append(TreeNode(postorder[-1]))\n",
    "        i = n - 2\n",
    "        inorderIndex = n-1\n",
    "        root = stack[0]\n",
    "        while i >= 0:\n",
    "            father = stack[-1]\n",
    "            if father.val ==  inorder[inorderIndex]:\n",
    "                while stack and stack[-1].val == inorder[inorderIndex]:\n",
    "                    father = stack.pop()\n",
    "                    inorderIndex -= 1\n",
    "                \n",
    "                node = TreeNode(postorder[i])\n",
    "                father.left = node\n",
    "                i -= 1\n",
    "                stack.append(node)\n",
    "            else:\n",
    "                node = TreeNode(postorder[i])\n",
    "                father.right = node\n",
    "                i -= 1\n",
    "                stack.append(node)\n",
    "        \n",
    "        print(root)\n",
    "\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.memo = {}\n",
    "        self.post = []\n",
    "\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        self.memo = {val:key for key,val in enumerate(inorder)}\n",
    "        self.post = postorder\n",
    "        \n",
    "        root = self.helper(0,len(inorder)-1,0,len(self.post)-1)\n",
    "        print(root)\n",
    "        return root\n",
    "        #root.val = slef.post\n",
    "\n",
    "    def helper(self,istart,iend,pstart,pend):\n",
    "        if istart > iend or pstart >pend :\n",
    "            return None       \n",
    "        root = self.post[pend] #根节点的值\n",
    "        root_inde = self.memo[root] #根节点的索引\n",
    "        node =TreeNode(root)\n",
    "        node.left = self.helper(istart,root_inde-1,pstart,pstart+root_inde-1-istart)\n",
    "        node.right = self.helper(root_inde+1,iend,pstart+root_inde-istart,pend-1)#不能单个引用i中的索引到p中，在p中可以用 P种的索引+在i中计算出的距离，即p，i中的索引并不是固定的是相对的，相互引用的时候只能引用距离，root_inde属于i中的索引可以在i中直接引用，在p中不可以\n",
    "        #pstart+root_inde-istart,pend-1)\n",
    "        return node \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:\n",
    "        self.now = len(postorder) - 1\n",
    "        dict_inorder = {}\n",
    "        for i in range(len(inorder)):\n",
    "            dict_inorder[inorder[i]] = i\n",
    "        return self.f(0, len(postorder) - 1, inorder, postorder, dict_inorder)\n",
    "    def f(self, start, end, inorder, postorder, dict_inorder):\n",
    "        if start > end:\n",
    "            return None\n",
    "        node = TreeNode(postorder[self.now])\n",
    "        self.now -= 1\n",
    "        index = dict_inorder[node.val]\n",
    "        node.right = self.f(index + 1, end, inorder, postorder, dict_inorder)\n",
    "        node.left = self.f(start, index - 1, inorder, postorder, dict_inorder)\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:\n",
    "        import numpy\n",
    "        ins = numpy.array(inorder)\n",
    "        pos = numpy.array(postorder)\n",
    "        def helper(l1, r1, l2, r2):\n",
    "            if l1 >= r1 or l2 >= r2:\n",
    "                return None\n",
    "            \n",
    "            val = pos[r2 - 1]\n",
    "\n",
    "            root = TreeNode(int(val))\n",
    "            # print(root)\n",
    "            idx = l1    \n",
    "            while idx < r1 and ins[idx] != val:\n",
    "                idx += 1\n",
    "    \n",
    "            distance = idx - l1\n",
    "            root.left = helper(l1, idx, l2, l2 + distance)\n",
    "            root.right = helper( idx+1, r1, l2+distance, r2-1)\n",
    "            return root\n",
    "        \n",
    "        return helper(0, len(ins), 0, len(pos))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "import numpy\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:\n",
    "\n",
    "        def build_a_tree(l,r):\n",
    "            if l>r:\n",
    "                return\n",
    "            node = postorder.pop()\n",
    "            root = TreeNode(node)\n",
    "            indx = inorder.index(node)\n",
    "            root.right = build_a_tree(indx+1,r)\n",
    "            root.left = build_a_tree(l,indx-1)\n",
    "            return root\n",
    "            \n",
    "        return build_a_tree(0,len(inorder)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, inorder, postorder):\n",
    "        \"\"\"\n",
    "        :type inorder: List[int]\n",
    "        :type postorder: List[int]\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if postorder==[] or inorder==[]:\n",
    "            return None\n",
    "        rootValue=postorder.pop()\n",
    "        root=TreeNode(rootValue)\n",
    "        index=inorder.index(rootValue)\n",
    "        root.right=self.buildTree(inorder[index+1:],postorder)\n",
    "        root.left=self.buildTree(inorder[:index],postorder)\n",
    "        return root\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, inorder, postorder):\n",
    "        \"\"\"\n",
    "        :type inorder: List[int]\n",
    "        :type postorder: List[int]\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        def helper(inorder, postorder):\n",
    "            if not inorder or not postorder:\n",
    "                return None\n",
    "\n",
    "            root_val = postorder.pop()\n",
    "            root = TreeNode(root_val)\n",
    "            idx = inorder.index(root_val)\n",
    "            \n",
    "            root.right = helper(inorder[idx+1:],postorder)\n",
    "            root.left = helper(inorder[:idx], postorder)\n",
    "\n",
    "            return root\n",
    "\n",
    "        return helper(inorder,postorder)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:\n",
    "        root = None\n",
    "        if inorder:\n",
    "            ind = inorder.index(postorder.pop())\n",
    "            root = TreeNode(inorder[ind])\n",
    "            root.right = self.buildTree(inorder[ind+1:], postorder)\n",
    "            root.left = self.buildTree(inorder[:ind], postorder)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:\n",
    "        self.postorder = postorder\n",
    "        self.len = len(postorder)\n",
    "        return self.recursion(inorder)\n",
    "\n",
    "    def recursion(self, inorder):\n",
    "        if not inorder:\n",
    "            return None\n",
    "        rootValue = 0\n",
    "        rootIndex = 0\n",
    "        for i in range(-1, -self.len-1, -1):\n",
    "            if self.postorder[i] in inorder:\n",
    "                rootIndex = i\n",
    "                rootValue = self.postorder[i]\n",
    "                break\n",
    "        else:\n",
    "            return None\n",
    "        self.postorder.pop(rootIndex)\n",
    "        self.len -= 1\n",
    "        rootIndex = inorder.index(rootValue)\n",
    "        leftInorder = inorder[:rootIndex]\n",
    "        rightInorder = inorder[rootIndex+1:]\n",
    "        root = TreeNode(rootValue)\n",
    "        root.left = self.recursion(leftInorder)\n",
    "        root.right = self.recursion(rightInorder)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:\n",
    "        if inorder:\n",
    "            ind = inorder.index(postorder.pop())\n",
    "            root = TreeNode(inorder[ind])\n",
    "            root.right = self.buildTree(inorder[ind+1:], postorder)\n",
    "            root.left = self.buildTree(inorder[:ind], postorder)\n",
    "            return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        root = TreeNode()\n",
    "        if inorder == [] or postorder == []:\n",
    "            return None\n",
    "        root.val=postorder.pop()\n",
    "        key = root.val\n",
    "        flag = 0\n",
    "        for i in range(len(inorder)):\n",
    "            if key == inorder[i]:\n",
    "                flag = i\n",
    "        root.right = self.buildTree(inorder[flag+1:],postorder)\n",
    "        root.left = self.buildTree(inorder[0:flag],postorder)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if len(inorder)==0:\n",
    "            return None\n",
    "        else:\n",
    "            value = postorder.pop()\n",
    "            index = inorder.index(value)\n",
    "            root = TreeNode(val = value)\n",
    "            root.right = self.buildTree(inorder[index+1:],postorder)\n",
    "            root.left = self.buildTree(inorder[:index],postorder)\n",
    "            return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        mem = {val: i for i, val in enumerate(inorder)}\n",
    "\n",
    "        def traverse(post_list, in_begin, in_end):\n",
    "            if not post_list:\n",
    "                return None\n",
    "            root = post_list[-1]\n",
    "            in_idx = mem[root]\n",
    "            left_len = in_idx - in_begin\n",
    "            right_len = in_end - in_begin - left_len\n",
    "            node = TreeNode(root)\n",
    "            node.left = traverse(post_list[0:left_len], in_begin, in_idx-1)\n",
    "            node.right = traverse(post_list[left_len:-1], in_idx+1, in_end)\n",
    "            return node\n",
    "\n",
    "        return traverse(postorder, 0, len(inorder)-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        root = TreeNode(postorder[-1])\n",
    "        self.inorderDic ={}\n",
    "        n = len(inorder)\n",
    "        for i in range(n):\n",
    "            self.inorderDic[inorder[i]] = i\n",
    "        def createTree(curPostorder):\n",
    "            postorder1 = []\n",
    "            postorder2 = []\n",
    "            rootVal = curPostorder.pop()\n",
    "            rootNode = TreeNode(rootVal)\n",
    "            for val in curPostorder:\n",
    "                if self.inorderDic[val] < self.inorderDic[rootVal]:\n",
    "                    postorder1.append(val)\n",
    "                else:\n",
    "                    postorder2.append(val)\n",
    "            if postorder1:\n",
    "                rootNode.left = createTree(postorder1)\n",
    "            if postorder2:\n",
    "                rootNode.right = createTree(postorder2)\n",
    "            return rootNode\n",
    "        return createTree(postorder)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        def judgeNode(split_list, preorder):\n",
    "            if len(split_list) == 1:  # 叶子结点则构造节点\n",
    "                node = TreeNode(split_list[0])\n",
    "                # print(split_list[0])\n",
    "                preorder.remove(split_list[0])\n",
    "                return node\n",
    "            elif len(split_list)>1:  # 不是叶子结点，则找出当前根节点\n",
    "                return constructNode(preorder[-1], preorder, split_list)\n",
    "            else:\n",
    "                return None\n",
    "\n",
    "        def constructNode(num, preorder, inorder):\n",
    "            # print(num)\n",
    "            node = TreeNode(num)\n",
    "            preorder.remove(num)\n",
    "            index = inorder.index(num)\n",
    "\n",
    "            # 划分中序的左右两段\n",
    "            split_left = inorder[:index]\n",
    "            split_right = inorder[index + 1:]\n",
    "            node.right = judgeNode(split_right, preorder)\n",
    "            node.left = judgeNode(split_left, preorder)\n",
    "            \n",
    "            return node\n",
    "\n",
    "        # 前序确定根节点，中序确定左右节点\n",
    "        head = constructNode(postorder[-1], postorder, inorder)\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        \n",
    "\n",
    "        def helper(inorder, postorder):\n",
    "            if not postorder or ( postorder[-1] not in inorder ):\n",
    "                return  \n",
    "            value= postorder.pop()\n",
    "            head = TreeNode(value)\n",
    "            \n",
    "            \n",
    "            chaifen = inorder.index(value) # 拆分的点\n",
    "\n",
    "            right = inorder[chaifen:]\n",
    "            left = inorder[:chaifen+1]\n",
    "\n",
    "            \n",
    "            head.right = self.buildTree(right, postorder)\n",
    "            head.left = self.buildTree(left, postorder)\n",
    "            return head\n",
    "        return helper(inorder, postorder)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # def helper(in_left, in_right):\n",
    "        #     # 如果这里没有节点构造二叉树了，就结束\n",
    "        #     if in_left > in_right:\n",
    "        #         return None\n",
    "            \n",
    "        #     # 选择 post_idx 位置的元素作为当前子树根节点\n",
    "        #     val = postorder.pop()\n",
    "        #     root = TreeNode(val)\n",
    "\n",
    "        #     # 根据 root 所在位置分成左右两棵子树\n",
    "        #     index = idx_map[val]\n",
    " \n",
    "        #     # 构造右子树\n",
    "        #     root.right = helper(index + 1, in_right)\n",
    "        #     # 构造左子树\n",
    "        #     root.left = helper(in_left, index - 1)\n",
    "        #     return root\n",
    "        \n",
    "        # # 建立（元素，下标）键值对的哈希表\n",
    "        # idx_map = {val:idx for idx, val in enumerate(inorder)} \n",
    "        # return helper(0, len(inorder) - 1)\n",
    "\n",
    "\n",
    "          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, x):\r\n",
    "#         self.val = x\r\n",
    "#         self.left = None\r\n",
    "#         self.right = None\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:\r\n",
    "        if inorder:\r\n",
    "            idx = inorder.index(postorder.pop())\r\n",
    "            root = TreeNode(inorder[idx])\r\n",
    "            root.right = self.buildTree(inorder[idx+1:], postorder)\r\n",
    "            root.left = self.buildTree(inorder[:idx], postorder)\r\n",
    "            return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, inorder, postorder):\n",
    "        \"\"\"\n",
    "        :type inorder: List[int]\n",
    "        :type postorder: List[int]\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not postorder:\n",
    "            return None\n",
    "        i = inorder.index(postorder[-1])\n",
    "        root=TreeNode(postorder[-1])\n",
    "        root.left=self.buildTree(inorder[:i], postorder[:i])\n",
    "        root.right=self.buildTree(inorder[i+1:],postorder[i:-1])\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, inorder, postorder):\n",
    "        \"\"\"\n",
    "        :type inorder: List[int]\n",
    "        :type postorder: List[int]\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not postorder:\n",
    "            return []\n",
    "        def digui(root, postorder, inorder):\n",
    "            root.val = postorder[-1]\n",
    "            node = postorder[-1]\n",
    "            index = inorder.index(node)\n",
    "            #如果有左子树:\n",
    "            if index>0:\n",
    "                root.left = TreeNode(0)\n",
    "                digui(root.left, postorder[:index], inorder[:index])\n",
    "            #如果有右子树:    \n",
    "            if index<len(inorder)-1:\n",
    "                root.right = TreeNode(0)\n",
    "                digui(root.right, postorder[index:len(postorder)-1], inorder[index+1:])\n",
    "                \n",
    "        root = TreeNode(0)        \n",
    "        digui(root, postorder, inorder)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:\n",
    "        if not len(inorder) or not len(postorder):\n",
    "            return None\n",
    "        nodeVal = postorder[-1]\n",
    "        node = TreeNode(nodeVal)\n",
    "        for idx, num in enumerate(inorder):\n",
    "            if num == nodeVal:\n",
    "                break\n",
    "        leftLen = idx\n",
    "        if leftLen:\n",
    "            node.left = self.buildTree(inorder[:leftLen], postorder[:leftLen])\n",
    "        rightLen = len(inorder) - leftLen - 1\n",
    "        if rightLen:\n",
    "            node.right = self.buildTree(inorder[idx+1:], postorder[leftLen:leftLen+rightLen])\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution(object):\n",
    "    def buildTree(self, inorder, postorder):\n",
    "        if not inorder and not postorder:\n",
    "            return None\n",
    "        root = postorder[-1]\n",
    "        for i in range(len(inorder)):\n",
    "            if inorder[i] == root:\n",
    "                break\n",
    "        left = self.buildTree(inorder[0:i],postorder[:i])\n",
    "        right = self.buildTree(inorder[1+i:],postorder[i:-1])\n",
    "        t = TreeNode(root)\n",
    "        t.left = left\n",
    "        t.right = right\n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:\n",
    "        if not inorder:return\n",
    "        else:\n",
    "            root = TreeNode(postorder[-1])\n",
    "            i = inorder.index(root.val)\n",
    "\n",
    "            root.left = self.buildTree(inorder[:i],postorder[:i])\n",
    "            root.right = self.buildTree(inorder[i+1:],postorder[i:-1])\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if len(inorder) == 0:\n",
    "            return\n",
    "        if len(inorder) == 1:\n",
    "            return TreeNode(inorder[0])\n",
    "        \n",
    "        root_val = postorder[-1]\n",
    "        index = inorder.index(root_val)\n",
    "        left = self.buildTree(inorder[:index], postorder[:index])\n",
    "        right = self.buildTree(inorder[index+1:], postorder[index:-1])\n",
    "        return TreeNode(root_val, left, right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not inorder:\n",
    "            return None\n",
    "        root=postorder[-1]\n",
    "        sep=inorder.index(root)\n",
    "        return TreeNode(root,self.buildTree(inorder[:sep],postorder[:sep]),self.buildTree(inorder[sep+1:],postorder[sep:-1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not postorder:\n",
    "            return None\n",
    "\n",
    "        root_val = postorder[-1]\n",
    "        root = TreeNode(root_val)\n",
    "\n",
    "        separate_idx = inorder.index(root_val)\n",
    "        separate_left = inorder[:separate_idx]\n",
    "        separate_right = inorder[separate_idx+1:]\n",
    "\n",
    "        postorder_left = postorder[:len(separate_left)]\n",
    "        postorder_right = postorder[len(separate_left):-1]\n",
    "\n",
    "        root.left = self.buildTree(separate_left, postorder_left)       \n",
    "        root.right = self.buildTree(separate_right, postorder_right)       \n",
    "\n",
    "        return root"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
